package AcWing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author ZhuYi
 * @create 2024/7/24 10:30
 */
public class 归并排序 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] strs = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(strs[i]);
        }
        mergeSort(arr, 0, n - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    /**
     * 实现归并排序。
     * 该方法使用递归的方式对数组的指定部分进行排序。它首先将数组分成两半，分别对每一半进行排序，
     * 然后将排序后的两半合并成一个有序的数组。
     *
     * @param arr 待排序的数组
     * @param l   左边界索引
     * @param r   右边界索引
     */
    public static void mergeSort(int[] arr, int l, int r) {
        // 如果左边界大于右边界，则表示区间内没有元素需要排序，直接返回
        if (l >= r) return;
        // 计算中间索引，将数组分成两半
        int mid = (l + r) / 2;
        // 递归地对左半部分进行排序
        mergeSort(arr, l, mid);
        // 创建一个临时数组，用于存储合并后的有序数组
        int[] tmp = new int[r - l + 1];
        // 递归地对右半部分进行排序
        mergeSort(arr, mid + 1, r);
        // 初始化两个指针，分别指向左半部分和右半部分的起始位置
        int k = 0, i = l, j = mid + 1;
        // 遍历左右两半部分，将较小的元素依次放入临时数组
        while (i <= mid && j <= r) {
            if (arr[i] < arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        // 处理左半部分剩余的元素
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        // 处理右半部分剩余的元素
        while (j <= r) {
            tmp[k++] = arr[j++];
        }
        // 将临时数组中的元素复制回原数组，完成排序
        for (i = l, j = 0; i <= r; i++, j++) {
            arr[i] = tmp[j];
        }
    }


}
